RS codes belong to linear block codes, and the construction and discovery of RS codes are considered as the perfect combination of theoretical mathematics and engineering implementation. RS codes have a powerful correcting ability and are the unique kind of applicable codes having the maximum inter-code distance. Therefore, RS codes have been widely used from information storage system, deep space communication to modern wireless communication.
In recent decades, the decoding of an RS code has always used hard-decision decoding, including mainly two big categories: BM (Boyer-Moore) algorithm and EMA (Exponential Moving Average) algorithm, which has a big loss in performance compared with soft-decision decoding. The fatal deficiency of RS codes is that no simple and efficient soft-decision decoding method has been found yet.
In recent years, the study on soft-decision decoding for RS codes has become a study hot topic and people have been devoted to seek an efficient soft-decision decoding method. In 2004, a relatively simple KV soft-decision decoding algorithm was disclosed, vide R. Kotter and A. Vardy, “Algebraic soft-decision decoding of Reed-Solomon codes IEEE” Trans. Inform. Theory, vol. 49, no. 11, pp. 2809-2825, November 2004. The algorithm is based on modern algebra and has polynomial complexity. However, since the algorithm involves interpolation and factorization of limited domain two-variable polynomial, its complexity is still high, and the algorithm is just suitable for the decoding for frequency domain encoding of RS codes and can not be applied directly to the time domain encoding of RS codes widely used in the current engineer applications. In the same year, an ABP (Adaptive Belief Propagation) soft-decision decoding algorithm was disclosed, vide J. Jiang and K. Narayanan, “Iterative soft decision decoding of Reed Solomon code based on adaptive parity check matrices,” in Proc. ISIT, 2004. ABP algorithm is an iteration decoding algorithm having good performance, and is one having the best performance among the known RS decoding algorithms. However, the kind of iteration decoding algorithm needs to perform Gaussian elimination and belief propagation algorithm of the check array in each iteration process, which has a high complexity, and it is now still in the stage of laboratory simulation, and there is still a long way to go before the algorithm is applied in engineering.
Therefore, the existing hard-decision decoding and soft-decision decoding method for RS codes has deficiencies such as high complexity, not suitable for time domain encoding and so on.